package alg;

public class Fw {
	private int[][] path; 
	private int size;
	public Fw(int n){
		path=new int[n][n];
		size=n;
		for (int i=0; i<n; i++)
		{
			path[i][i] = 1;
		}
	}

	public void insert(int i, int j){
		//System.out.println("insert: "+i+","+j);
		path[i][j]=1;
		//return countTrans();
	}
	public void delete(int i, int j){
		//System.out.println("delete: "+i+","+j);
		if (i == j)
			return;
		path[i][j]=0;
		//return countTrans();
	}

	public int countTrans(){
		int[][] trans = floydWarshall();
		int count=0;
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				count+=trans[i][j];
			}
		}
		
		//System.out.println("c="+count);
		return count;
	}

	private int[][] floydWarshall(){
		int[][] fw = new int[size][size];
		for (int i=0; i<size; i++)
		{
			for (int j=0; j<size; j++)
				fw[i][j] = path[i][j];
		}
		for (int k=0;k<size;k++){
			for(int i=0;i<size;i++){
				for (int j=0;j<size;j++){
					if(fw[i][j]!=1 && (fw[i][k]+fw[k][j])>1){
						fw[i][j]=1;
					}
				}
			}
		}
		
		return fw;
	}
}



/*12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );*/